package com.hanxiaozhang.heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 〈一句话功能简述〉<br>
 * 〈动态堆〉
 *
 * @author hanxinghua
 * @create 2021/9/15
 * @since 1.0.0
 */
public class DynamicHeap<T> {


    public static void main(String[] args) {

        System.out.println("----- PriorityQueue 实现的最小堆：-----");
        Student s1 = new Student(2, 50, 11111);
        Student s2 = new Student(1, 60, 22222);
        Student s3 = new Student(6, 10, 33333);
        Student s4 = new Student(3, 20, 44444);

        PriorityQueue<Student> heap = new PriorityQueue<>(new StudentComparator());
        heap.add(s1);
        heap.add(s2);
        heap.add(s3);
        heap.add(s4);

        while (!heap.isEmpty()) {
            Student cur = heap.poll();
            System.out.println(cur.toString());
        }

        System.out.println("----- DynamicHeap 实现的最小堆：-----");

        DynamicHeap<Student> myHeap = new DynamicHeap<>(new StudentComparator());
        myHeap.push(s1);
        myHeap.push(s2);
        myHeap.push(s3);
        myHeap.push(s4);

        while (!myHeap.isEmpty()) {
            Student cur = myHeap.pop();
            System.out.println(cur.toString());
        }

        System.out.println("----- PriorityQueue 修改实体内容：-----");

        s1 = new Student(2, 50, 11111);
        s2 = new Student(1, 60, 22222);
        s3 = new Student(6, 10, 33333);
        s4 = new Student(3, 20, 44444);

        heap = new PriorityQueue<>(new StudentComparator());
        heap.add(s1);
        heap.add(s2);
        heap.add(s3);
        heap.add(s4);

        s2.age = 6;
        s4.age = 12;


        while (!heap.isEmpty()) {
            Student cur = heap.poll();
            System.out.println(cur.toString());
        }

        System.out.println("----- DynamicHeap 修改实体内容：-----");

        s1 = new Student(2, 50, 11111);
        s2 = new Student(1, 60, 22222);
        s3 = new Student(6, 10, 33333);
        s4 = new Student(3, 20, 44444);

        myHeap = new DynamicHeap<>(new StudentComparator());

        myHeap.push(s1);
        myHeap.push(s2);
        myHeap.push(s3);
        myHeap.push(s4);

        s2.age = 6;
        myHeap.resign(s2);
        s4.age = 12;
        myHeap.resign(s4);

        while (!myHeap.isEmpty()) {
            Student cur = myHeap.pop();
            System.out.println(cur.toString());
        }

    }


    /**
     * 动态数组
     */
    private ArrayList<T> heap;

    /**
     * 记录对象的位置
     */
    private HashMap<T, Integer> indexMap;

    /**
     * 已经堆排序的大小
     */
    private int heapSize;

    /**
     * 比较器
     */
    private Comparator<? super T> comparator;

    public DynamicHeap(Comparator<? super T> com) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comparator = com;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int size() {
        return heapSize;
    }

    public boolean contains(T key) {
        return indexMap.containsKey(key);
    }

    /**
     * 添加
     *
     * @param value
     */
    public void push(T value) {
        heap.add(value);
        indexMap.put(value, heapSize);
        heapInsert(heapSize++);
    }

    /**
     * 弹出
     *
     * @return
     */
    public T pop() {
        T ans = heap.get(0);
        int end = heapSize - 1;
        swap(0, end);
        heap.remove(end);
        indexMap.remove(ans);
        heapify(0, --heapSize);
        return ans;
    }

    /**
     * 重新调整
     *
     * @param value
     */
    public void resign(T value) {
        int valueIndex = indexMap.get(value);
        heapInsert(valueIndex);
        heapify(valueIndex, heapSize);
    }

    private void heapInsert(int index) {
        while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void heapify(int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && (comparator.compare(heap.get(left + 1), heap.get(left)) < 0)
                    ? left + 1
                    : left;
            largest = comparator.compare(heap.get(largest), heap.get(index)) < 0 ? largest : index;
            if (largest == index) {
                break;
            }
            swap(largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    private void swap(int i, int j) {
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        heap.set(i, o2);
        heap.set(j, o1);
        indexMap.put(o1, j);
        indexMap.put(o2, i);
    }
}


class Student {
    public int classNo;
    public int age;
    public int id;

    public Student(int classNo, int age, int id) {
        this.classNo = classNo;
        this.age = age;
        this.id = id;
    }


    @Override
    public String toString() {
        return "Student{" +
                "classNo=" + classNo +
                ", age=" + age +
                ", id=" + id +
                '}';
    }
}


class StudentComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.age - o2.age;
    }

}